/**
 * Created by zhourh on 2018/9/19.
 *
 * 给定一个二叉树，计算整个树的坡度。

 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

 整个树的坡度就是其所有节点的坡度之和。

 示例:

 输入:
 1
 /   \
 2     3
 输出: 1
 解释:
 结点的坡度 2 : 0
 结点的坡度 3 : 0
 结点的坡度 1 : |2-3| = 1
 树的坡度 : 0 + 0 + 1 = 1
 注意:

 任何子树的结点的和不会超过32位整数的范围。
 坡度的值不会超过32位整数的范围。

 */
public class BinaryTreeTilt {

    public static void main(String[] args) {
        System.out.println(new BinaryTreeTilt().findTilt2(Converter.convertArray2TreeNode(new Integer[]{1,2,3})));
        System.out.println(new BinaryTreeTilt().findTilt2(Converter.convertArray2TreeNode(new Integer[]{1,2,3,4,5,6,7})));
    }

    int tilt = 0;

    public int findTilt2(TreeNode root) {
        sum(root);
        return tilt;
    }

    public int sum(TreeNode root) {

        if (root == null){
            return 0;
        }

        int sumLeft = sum(root.left);
        int sumRight = sum(root.right);

        tilt += Math.abs(sumLeft - sumRight);

        return sumLeft + sumRight + root.val;

    }

    public int findTilt(TreeNode root) {
        dfsSum(root);
        return findTiltInternal(root);
    }

    private int findTiltInternal(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftValue = node.left != null ? node.left.val : 0;
        int rightValue = node.right != null ? node.right.val : 0;
        return findTiltInternal(node.left) + findTiltInternal(node.right) + Math.abs(leftValue - rightValue);
    }

    private void dfsSum(TreeNode node) {

        if (node == null) {
            return;
        }
        if (node.left != null) {
            dfsSum(node.left);
            node.val += node.left.val;
        }

        if (node.right != null) {
            dfsSum(node.right);
            node.val += node.right.val;
        }
    }
}
